#!/usr/bin/env python


# Configurable parameters
# - count of nodes
# - number of buddies for each node (optimally)
# - percent of network loss
# - run time
# - random seed (reproduction)

# * Buddy attribute is mutual (a is buddy of b if b is buddy of a)
# * OFFLINE transitions cannot be communicated (directly) strategies:
#  - message passing failure indicates OFFLINE transition for node
#       * obviously could be dropped message
#  - keep-alive
#  - repeated net passing failure (require a threshold)
#  - heard about it ( rumor of either of above )
#  - combination of above (threshold of rumors)
# * ONLINE event
#  - direct messaging
#  - rumor messaging

# * Strategies
#   - rumoring or no     [ chose YES (configurable) ]
#   - offline rumoring   [ YES (configurable) ]
#   - message tx success implies peer ONLINE? [NO, could be done]
#   - message tx failure implies peer OFFLINE? [ YES, keep-alive not implemented ]
#   - last state of buddies is cached on OFFLINE/ONLINE transition

import sched
from optparse import OptionParser
import random
import time
import sys

useRumors = False
debug = False

def pdebug( s ):
    if debug:
        print s

runTime = 0
startTime = time.time()
states = [ "OFFLINE", "ONLINE" ]
currentTime = 0
percentComplete = 0
def timeFunc() :
    return currentTime
def delayFunc( delay ) :
    global currentTime
    if not debug:
        global percentComplete
        percent = runTime / 100
        if ( currentTime / percent > percentComplete ):
            percentComplete = currentTime / percent
            print "\r%d"%(percentComplete),
    sys.stdout.flush( )
    currentTime = currentTime + delay
scheduler = sched.scheduler( timeFunc, delayFunc )

def mapBuddies( nNodes, nBuddies ):
    "Create map of mutual buddies. Creates list of set of buddies such that"
    " if a is buddy of b, then b is buddy of a"
    valid = False
    while not valid: # ensure every node has at least 1 buddy
        valid = True
        buddies = []
        nodes = set( range(0,nNodes) )
        for i in range( 0, nNodes ):
            buddies.append( [] )
        for i in range( 0, nNodes ):
            nodes.discard( i )
            need = min( len(nodes), nBuddies - len( buddies[i] ) )
            newSet = random.sample( nodes, need )
            buddies[i].extend( newSet )
            for n in newSet:
                buddies[n].append(i)
                if ( len( buddies[n] ) >= nBuddies ):
                    nodes.discard( n )
        for i in range( 0, nNodes ):
            if len( buddies[i]) == 0:
                valid = False
    return buddies

class Node:
    def state( self ): return self.state_
    def eventTime( self ): return self.event["time"]
    def buddies( self ): return self.buddies_
    def buddyIds( self ): return self.buddies().keys()
    def buddyState( self, id ): return self.buddies_[id]['presence']
    def buddyEventTime( self, id ): return self.buddies_[id]['time']
    def id( self ): return self.id_
    def setBuddyState( self, id, eventTime, state ):
        self.buddies_[id] = { 'time': eventTime, 'presence' : state }

    def __init__( self, id, simulator, buddies ):
        self.id_ = id
        self.state_ = random.randint( 0, 1 )
        self.simulator = simulator
        self.buddies_ = {}
        map( self.addBuddy, buddies )
        self.scheduleMessage( 12 )

    def addBuddy( self, id ):
        self.setBuddyState( id, -1, 0 )

    def scheduleMessage( self, delay ):
        # Strategy: even timing
        scheduler.enter( delay, 0,
                         self.doMessage, () )

    def stateChange( self ):
        self.state_ = ( self.state_ + 1 ) % 2
        pdebug( "%d  [%d] : %s" % ( self.id(), currentTime, states[self.state_] ) )
        self.event = {}
        self.event["time"] = currentTime
        if ( 1 == self.state_ ):
            self.event["buddies"] = [ e for e in self.buddyIds() ]

    def chooseBuddy( self ):
        # Strategy: round-robin
        if ( len( self.event["buddies"] ) == 0 ):
            self.event["buddies"] = self.buddyIds()
        return self.event["buddies"].pop()

    def doMessage( self ):
        if ( self.state_ == 1 ):
            self.simulator.message( self.id(), self.chooseBuddy() ) 
        self.scheduleMessage( 12 )

    def onMessage( self, peer ):
        # Assumed this node can see all state of sending peer (contents of msg)
        # returns lists of conclusions [ [ peer, latency, state ], ... ]

        # Checks
        if 0 == self.state():
            raise Exception("Message while OFFFLINE")
        if 0 == peer.state():
            raise Exception("Message from OFFLINE peer")
        if ( peer.id() not in self.buddyIds() ):
            raise Exception("Message from non-buddy")

        pdebug( "%d [ %d ] message <- %d" % ( self.id(), currentTime, peer.id() ) )

        conclusions = []
        if ( peer.eventTime() != self.buddyEventTime( peer.id() ) or
             peer.state() != self.buddyState( peer.id() ) ):
            latency = currentTime - max( [ peer.eventTime(), self.eventTime() ] )
            conclusions.append( [ peer.id(), latency, peer.state() ] )
            self.setBuddyState( peer.id(), peer.eventTime(), 1 )

        # Can put rumors here (this node checks states of all of
        # peer's peer states and concludes things about his buddies.
        # Likewise, since protocol decided bi-directional, could allow
        # peer to see this state.

        if not useRumors:
            return conclusions

        for rumorId in set( peer.buddyIds() ).intersection( self.buddyIds() ):
            if ( ( peer.buddyEventTime( rumorId ) > self.buddyEventTime( rumorId ) ) ):
                latency = currentTime - max( [ peer.buddyEventTime( rumorId ), self.eventTime()])
                conclusions.append( [ rumorId, latency, peer.buddyState( rumorId ) ] )
                self.setBuddyState( rumorId, peer.buddyEventTime( rumorId ), peer.buddyState( rumorId ))

        return conclusions

    def onFailedMessage( self, id ):
        # *NO* access to peers state
        conclusions = []
        if ( self.buddyState( id ) ):
            self.setBuddyState( id, currentTime, 0 )
            conclusions.append( id )
        return conclusions

class Simulator:
    def __init__( self, options ):
        print "Seed : %s" % ( options.seed )
        self.average = 0.0
        self.stateChanges = 0
        self.messages = 0
        self.goodConclusions = 0
        self.droppedMessages = 0
        self.badConclusions = 0
        self.missedOnlineTransitions = 0
        self.missedOfflineTransitions = 0
        self.targetNotifications = 0
        self.netLoss = min( [options.netLossPercent, 100] ) / 100.0
        print "Net Loss : %f" % ( self.netLoss )
        random.seed( options.seed )
        scheduler.enter( options.runTime, 0, self.exit, () )
        self.nodes = []
        buddyMap = mapBuddies( options.nodeCount, options.buddyCount )
        for i in range( 0, options.nodeCount ):
            self.nodes.append( Node( i, self, buddyMap[i] ) )
        map( self.stateChange, self.nodes )

    def scheduleStateChange( self, node ):
        scheduler.enter( random.randint( 0, 4000 ), 0,
                         self.stateChange, [ node ] )

    def stateChange( self, node ):
        # counters: missed counters are not 100% correct but offer some idea.
        self.targetNotifications += len(node.buddies())
        for id in node.buddies():
            if self.nodes[id].state() != node.state():
                if ( node.state() ):
                    self.missedOnlineTransitions += 1
                else:
                    self.missedOfflineTransitions += 1
        self.stateChanges += 1

        node.stateChange()
        self.scheduleStateChange( node )

    def run( self ):
        global scheduler
        scheduler.run()

    def updateAverage( self, timeToLearn ):
        self.average = float(( timeToLearn + ( self.goodConclusions - 1 ) * self.average ) / 
                             self.goodConclusions )

    def message( self, src, dst ):
        randomNetLoss = random.random()
        if ( 0 == self.nodes[dst].state()
             or randomNetLoss < self.netLoss
             ):
            if randomNetLoss < self.netLoss:
                pdebug( "DROPPED [ %d ] message %d -> %d" % ( currentTime, src, dst ) )
            for id in self.nodes[ src ].onFailedMessage( dst ):
                if ( self.nodes[ id ].state() == 0 ):
                    self.goodConclusions += 1
                    latency = currentTime - self.nodes[ id ].eventTime()
                    pdebug( "%d learned of %d %s after %d" % ( src, id, "OFFLINE", latency ) )
                    self.updateAverage( latency )
                else:
                    self.badConclusions += 1
            return False

        self.messages += 1
        for conclusion in ( self.nodes[dst].onMessage( self.nodes[ src ] ) + 
                            self.nodes[src].onMessage( self.nodes[ dst ] ) ):
            ( id, latency, state ) = conclusion
            if ( self.nodes[id].state() == state ):
                pdebug( "%d learned of %d %s after %d" % ( dst, id, "ONLINE", latency ) )
                self.goodConclusions += 1
                self.updateAverage( latency )
            else:
                self.badConclusions += 1
        return True

    def exit( self ):
        print
        print "       Average learn  : %ds (%f minutes)" % ( self.average, 
                                                            float(self.average)/60 )
        print "    Messages per min  : %d" % ( float(self.messages) / (float(currentTime)/60) )

        print 
        print "        State Changes : %d" % ( self.stateChanges )        
        print " Target Notifications : %d" % ( self.targetNotifications )
        print "Missed Offline/Online : %d/%d"%( self.missedOfflineTransitions,
                                                self.missedOnlineTransitions )
        print "             Elapsed  : %ds" % ( currentTime )
        print "Good/Bad Conclusions  : %d/%d" % ( self.goodConclusions, self.badConclusions )
        print "            Messages  : %d" % ( self.messages )
        print "done"
        exit()

def main():
    parser = OptionParser()
    parser.add_option( "-n", "--nodes", 
                       dest="nodeCount", 
                       default=10,
                       type="int",
                       help="number of nodes" )
    parser.add_option( "-b", "--buddies", 
                       dest="buddyCount",
                       default=2,
                       type="int",
                       help="number of buddies per node",
                       )
    parser.add_option( "-s", "--seed",
                       dest="seed",
                       default=int(time.time()),
                       type="int",
                       help="seed to srand (for reproducing results)"
                       )
    parser.add_option( "-l", "--loss",
                       dest="netLossPercent",
                       default=5,
                       type="int",
                       help="Network loss percentage",
                       )
    parser.add_option( "-t", "--time",
                       dest="runTime",
                       default=36000, # 10 hours
                       type="int",
                       help="Time to run simulation.",
                       )
    parser.add_option( "-d", "--debug",
                       dest="debug",
                       default=False,
                       action="store_true",
                       help="Debug messages."
                       )
    parser.add_option( "-r", "--rumoring",
                       dest="rumoring",
                       default=False,
                       action="store_true",
                       help="Use rumors."
                       )
    
    (options, args) = parser.parse_args()
    global runTime, debug, useRumors
    debug = options.debug
    runTime = options.runTime
    useRumors = options.rumoring
    simulator = Simulator( options )
    simulator.run()

if __name__ == "__main__":
    main()
